{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "class Solution:\n",
    "    def restoreIpAddresses(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        result = []\n",
    "        addr = [0]*4\n",
    "        def recursion(start = 0, k = 0):\n",
    "            for i in range( 1, min(3, n-start)+1 ):\n",
    "                addr[k] = int(s[start:start+i])\n",
    "                if( addr[k] > 255 or i > 1 and s[start] == '0'): #2和3位地址不能以0开头\n",
    "                    return\n",
    "                if(k == 3 and start + i == n):\n",
    "                        result.append( '.'.join([str(x) for x in addr]) )\n",
    "                elif(k < 3):\n",
    "                    recursion(start+i, k+1)\n",
    "        recursion()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['1.1.1.255', '1.1.12.55', '1.1.125.5', '1.11.2.55', '1.11.25.5', '1.112.5.5', '11.1.2.55', '11.1.25.5', '11.12.5.5', '111.2.5.5']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'2.3.4.5'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = Solution()\n",
    "s = \"25525511135\"\n",
    "s = '111255'\n",
    "print(a.restoreIpAddresses(s))\n",
    "'.'.join([str(x) for x in[2,3,4,5]])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
